/*
 * @lc app=leetcode.cn id=416 lang=java
 *
 * [416] 分割等和子集
 *
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (43.74%)
 * Likes:    172
 * Dislikes: 0
 * Total Accepted:    14.1K
 * Total Submissions: 32.2K
 * Testcase Example:  '[1,5,11,5]'
 *
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意:
 *
 *
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 *
 *
 * 示例 1:
 *
 * 输入: [1, 5, 11, 5]
 *
 * 输出: true
 *
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *
 *
 *
 *
 * 示例 2:
 *
 * 输入: [1, 2, 3, 5]
 *
 * 输出: false
 *
 * 解释: 数组不能分割成两个元素和相等的子集.
 *
 *
 *
 *
 */

// @lc code=start
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int n : nums) {
            sum += n;
        }
        if(sum % 2 != 0) {
            return false;
        }
        boolean dp[] = new boolean[sum/2 + 1];
        dp[0] = true;
        for(int i =0;i<nums.length; i++) {
            for(int j=sum/2 ; j > 0; j--) {
                if(dp[j] || j-nums[i]>-1 && dp[j-nums[i]]) {
                    dp[j] = true;
                }
            }
        }
        return dp[sum/2];
    }
}
// @lc code=end

